//给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。 
//
// 
//
// 示例 1： 
//
// 
//输入：head = [1,2,3,3,4,4,5]
//输出：[1,2,5]
// 
//
// 示例 2： 
//
// 
//输入：head = [1,1,1,2,3]
//输出：[2,3]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点数目在范围 [0, 300] 内 
// -100 <= Node.val <= 100 
// 题目数据保证链表已经按升序 排列 
// 
// Related Topics 链表 双指针 👍 921 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution82 {

    /**
     * 解题思路：
     * 1.利用双指针位移思路，操作first指针的next节点，指向下一个不重复的节点
     * 2.如果last节点是重复的，则last一直后移直到找到不重复的一个节点，将first.next指向他
     * 3.如果last节点是不重复的，则first节点也后移一位
     * 4.last节点需要一直后移
     * <p>
     * 执行耗时:0 ms,击败了100.00% 的Java用户
     * 内存消耗:40.9 MB,击败了59.09% 的Java用户
     */
    public ListNode deleteDuplicates(ListNode head) {
        ListNode root = new ListNode();
        root.next = head;
        ListNode first = root;
        ListNode last = root.next;
        while(last != null && last.next != null && first != null) {
            if(last.val == last.next.val) {
                int sameVal = last.val;
                while(last.next != null && last.next.val == sameVal) {
                    last = last.next;
                }
                first.next = last.next;
            } else {
                first = first.next;
            }
            last = last.next;
        }
        return root.next;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
